package sort.mergeSort;

/**
 * @Description
 * @Author Firenut
 * @Date 2023-02-08 15:45
 */
public class mergeSort {
    // ans只是作为一个辅助数组，用于存放合并后的结果，
    // 最终要写回nums[],而且是涉及到递归,并非直接在ans数组操作，
    // 否则就成了插入排序了
    int[] ans;

    public int[] sortArray(int[] nums) {
        ans = new int[nums.length];
        sort(nums, 0, nums.length - 1);
        return ans;
    }

    void sort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        sort(nums, start, mid);
        sort(nums, mid + 1, end);
        merge(nums, start, mid, end);
    }

    void merge(int[] nums, int start, int mid, int end) {
        int p1 = start;
        int p2 = mid + 1;

        // int p3 = start;
        int p3 = 0; // ****
        while (p1 <= mid && p2 <= end) {
            if (nums[p1] < nums[p2]) {
                ans[p3++] = nums[p1++];
            } else {
                ans[p3++] = nums[p2++];
            }
        }
        while (p1 <= mid) {
            ans[p3++] = nums[p1++];
        }
        while (p2 <= end) {
            ans[p3++] = nums[p2++];
        }
        // 把合并后的临时有序数组迁移到最终的数组上
        for (int k = 0; k < end - start + 1; k++) {
            nums[k + start] = ans[k]; // *** 注意这个偏移量是k+start
        }
    }
}
